package me.seu.demo.algorithms;

import java.util.Arrays;

/**
 * 快速排序
 *
 * @author liangfeihu
 * @since 2021/2/18 上午11:50
 */
public class QuickSort {

    /**
     * 快速排序算法
     *
     * @param array
     */
    public static void quickSort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    /**
     * 快速排序算法
     *
     * @param array
     * @param left
     * @param right
     */
    private static void quickSort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        //int pivot = partition(array, left, right);
        int pivot = partitionV2(array, left, right);
        quickSort(array, left, pivot - 1);
        quickSort(array, pivot + 1, right);
    }

    /**
     * 单边循环（推荐写法）
     *
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int partition(int[] array, int left, int right) {
        int pivot = array[left];
        int mark = left;
        for (int i = left + 1; i <= right; i++) {
            if (array[i] < pivot) {
                mark++;
                int temp = array[i];
                array[i] = array[mark];
                array[mark] = temp;
            }
        }
        int temp = array[mark];
        array[mark] = pivot;
        array[left] = temp;

        return mark;
    }

    /**
     * 双边循环
     *
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int partitionV2(int[] array, int left, int right) {
        int pivot = array[left];
        int l = left;
        int r = right;
        // while (l < r) {
        while (l != r) {
            while (l < r && array[r] > pivot) {
                r--;
            }
            while (l < r && array[l] <= pivot) {
                l++;
            }

            if (l < r) {
                int temp = array[l];
                array[l] = array[r];
                array[r] = temp;
            }
        }

        array[left] = array[l];
        array[l] = pivot;

        return l;
    }

    /**
     * 冒泡排序算法
     *
     * @param array
     */
    public static void bubbleSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }
        int length = array.length;
        for (int i = 0; i < length - 1 - 1; i++) {
            boolean flag = false;
            for (int j = 0; j < length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    flag = true;
                }
            }
            if (!flag) {
                return;
            }
        }
    }

    public static void quickSortV2(int[] arr, int low, int high) {
        int i, j, temp, t;
        if (low > high) {
            return;
        }
        i = low;
        j = high;
        //temp就是基准位
        temp = arr[low];

        while (i < j) {
            //先看右边，依次往左递减
            while (temp <= arr[j] && i < j) {
                j--;
            }
            //再看左边，依次往右递增
            while (temp >= arr[i] && i < j) {
                i++;
            }
            //如果满足条件则交换
            if (i < j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
        }

        //最后将基准为与i和j相等位置的数字交换
        arr[low] = arr[i];
        arr[i] = temp;

        //System.out.println("i=" + i + ", j=" + j);
        //System.out.println(Arrays.toString(arr));
        //递归调用左半数组
        quickSortV2(arr, low, j - 1);
        //递归调用右半数组
        quickSortV2(arr, j + 1, high);
    }

    public static void main(String[] args) {
        int[] arr = new int[]{4, 4, 6, 5, 3, 2, 8, 1};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));

        int[] arr2 = new int[]{4, 6, 1, 3, 1, 9, 6, 7, 3, 8};
        quickSort(arr2);
        System.out.println(Arrays.toString(arr2));

        int[] arr3 = new int[]{4, 6, 1, 3, 1, 9, 6, 7, 3, 8};
        bubbleSort(arr3);
        System.out.println(Arrays.toString(arr3));

        int[] arr4 = new int[]{10, 7, 2, 4, 7, 62, 3, 4, 2, 1, 8, 9, 19};
        quickSortV2(arr4, 0, arr4.length - 1);
        System.out.println(Arrays.toString(arr4));
    }

}
